package com.leetcode.linklist;

import java.util.HashSet;
import java.util.Set;

/**
 * @author ：HBZ
 * @date ：Created in 2020/12/25 15:36
 * @description：
 * @modified By：
 */
public class Main {
    public static void main(String[] args) {
        ListNode head=new ListNode(1);
        ListNode node1=new ListNode(2);
        ListNode node2=new ListNode(3);
        ListNode node3=new ListNode(4);
        head.next=node1;
        node1.next=node2;
        node2.next=node3;
        node3.next=node1;
        System.out.println(hasCycle1(head));
        System.out.println(hasCycle2(head));
        System.out.println(hasCycle3(head));
    }
    public static boolean hasCycle1(ListNode head) {
        ListNode cur=head;
        Set<ListNode> set=new HashSet<>();
        while(cur!=null){
            if(set.contains(cur)){
                return true;
            }
            set.add(cur);
            cur=cur.next;
        }
        return false;
    }
    public static boolean hasCycle2(ListNode head) {
        if(head==null || head.next==null){
            return false;
        }
        ListNode fast=head;
        ListNode slow=head;
        do{
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                return true;
            }
        }
        while(fast!=null && fast.next!=null);
        return false;
    }
    public static boolean hasCycle3(ListNode head) {
        if(head==null || head.next==null){
            return false;
        }
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null && fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                return true;
            }
        }
        return false;
    }
}
